<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  
  <title>算法设计与分析实验三-动态规划 | hatena</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
  <meta name="description" content="实验项目：分治法的应用实验目的掌握动态规划算法的应用。 一、实验内容 最大子段和问题：给定由n个整数组成的序列，求其连续子段的最大和。 矩阵连乘问题：给定n个矩阵{A1, A2, …, An}，求最佳计算次序以最小化数乘次数。 双核CPU任务调度问题：给定n个任务及其处理时长，设计调度方案使CPU处理完所有任务所需时间最短。  二、问题分析">
<meta property="og:type" content="article">
<meta property="og:title" content="算法设计与分析实验三-动态规划">
<meta property="og:url" content="https://gitee.com/lanceluot/blog.git/2024/05/01/%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E4%B8%8E%E5%88%86%E6%9E%90%E5%AE%9E%E9%AA%8C%E4%B8%89-%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/index.html">
<meta property="og:site_name" content="hatena">
<meta property="og:description" content="实验项目：分治法的应用实验目的掌握动态规划算法的应用。 一、实验内容 最大子段和问题：给定由n个整数组成的序列，求其连续子段的最大和。 矩阵连乘问题：给定n个矩阵{A1, A2, …, An}，求最佳计算次序以最小化数乘次数。 双核CPU任务调度问题：给定n个任务及其处理时长，设计调度方案使CPU处理完所有任务所需时间最短。  二、问题分析">
<meta property="og:locale" content="zn_CN">
<meta property="article:published_time" content="2024-05-01T06:06:06.000Z">
<meta property="article:modified_time" content="2024-05-01T06:16:02.645Z">
<meta property="article:author" content="myself">
<meta property="article:tag" content="实验3">
<meta name="twitter:card" content="summary">
  
    <link rel="alternate" href="/blog/atom.xml" title="hatena" type="application/atom+xml">
  
  
    <link rel="shortcut icon" href="/blog/favicon.png">
  
  
    
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/typeface-source-code-pro@0.0.71/index.min.css">

  
  
<link rel="stylesheet" href="/blog/css/style.css">

  
    
<link rel="stylesheet" href="/blog/fancybox/jquery.fancybox.min.css">

  
  
<meta name="generator" content="Hexo 6.3.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/blog/" id="logo">hatena</a>
      </h1>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"><span class="fa fa-bars"></span></a>
        
          <a class="main-nav-link" href="/blog/">Home</a>
        
          <a class="main-nav-link" href="/blog/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
        
          <a class="nav-icon" href="/blog/atom.xml" title="RSS Feed"><span class="fa fa-rss"></span></a>
        
        <a class="nav-icon nav-search-btn" title="Suche"><span class="fa fa-search"></span></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Suche"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="https://gitee.com/lanceluot/blog.git"></form>
      </div>
    </div>
  </div>
</header>

      <div class="outer">
        <section id="main"><article id="post-算法设计与分析实验三-动态规划" class="h-entry article article-type-post" itemprop="blogPost" itemscope itemtype="https://schema.org/BlogPosting">
  <div class="article-meta">
    <a href="/blog/2024/05/01/%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E4%B8%8E%E5%88%86%E6%9E%90%E5%AE%9E%E9%AA%8C%E4%B8%89-%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/" class="article-date">
  <time class="dt-published" datetime="2024-05-01T06:06:06.000Z" itemprop="datePublished">2024-05-01</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="p-name article-title" itemprop="headline name">
      算法设计与分析实验三-动态规划
    </h1>
  

      </header>
    
    <div class="e-content article-entry" itemprop="articleBody">
      
        <h3 id="实验项目：分治法的应用"><a href="#实验项目：分治法的应用" class="headerlink" title="实验项目：分治法的应用"></a>实验项目：分治法的应用</h3><h4 id="实验目的"><a href="#实验目的" class="headerlink" title="实验目的"></a>实验目的</h4><p>掌握动态规划算法的应用。</p>
<h4 id="一、实验内容"><a href="#一、实验内容" class="headerlink" title="一、实验内容"></a>一、实验内容</h4><ol>
<li><strong>最大子段和问题</strong>：给定由n个整数组成的序列，求其连续子段的最大和。</li>
<li><strong>矩阵连乘问题</strong>：给定n个矩阵{A1, A2, …, An}，求最佳计算次序以最小化数乘次数。</li>
<li><strong>双核CPU任务调度问题</strong>：给定n个任务及其处理时长，设计调度方案使CPU处理完所有任务所需时间最短。</li>
</ol>
<h4 id="二、问题分析"><a href="#二、问题分析" class="headerlink" title="二、问题分析"></a>二、问题分析</h4><span id="more"></span>

<ol>
<li><strong>最大子段和问题</strong>：使用动态规划方法，状态转移方程为dp[i] &#x3D; max(dp[i-1] + a[i], a[i])。</li>
<li><strong>矩阵连乘问题</strong>：使用动态规划方法，状态转移方程为dp[i][j] &#x3D; min(dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j])。</li>
<li><strong>双核CPU任务调度问题</strong>：转化为01背包问题，状态转移方程为dp[i][j] &#x3D; max(dp[i-1][j], dp[i-1][j-a[i]] + a[i])。</li>
</ol>
<h4 id="三、数据结构定义"><a href="#三、数据结构定义" class="headerlink" title="三、数据结构定义"></a>三、数据结构定义</h4><ol>
<li><strong>最大子段和问题</strong>：Int dp[i] &#x2F;&#x2F; 以a[i]结尾的子段和</li>
<li><strong>矩阵连乘问题</strong>：Int dp[i][j] &#x2F;&#x2F; A[i:j]的最少乘次</li>
<li><strong>双核CPU任务调度问题</strong>：Int dp[i][j] &#x2F;&#x2F; 前i个任务分配给两个处理器后，处理器1的处理量</li>
</ol>
<h4 id="四、算法伪代码描述"><a href="#四、算法伪代码描述" class="headerlink" title="四、算法伪代码描述"></a>四、算法伪代码描述</h4><ol>
<li><strong>最大子段和问题</strong>：</li>
</ol>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">Copy CodemaxSum = currentSum = a[0]</span><br><span class="line">for i from 1 to n-1:</span><br><span class="line">    currentSum = max(currentSum + a[i], a[i])</span><br><span class="line">    maxSum = max(maxSum, currentSum)</span><br><span class="line">return maxSum</span><br></pre></td></tr></table></figure>

<ol>
<li><strong>矩阵连乘问题</strong>：</li>
</ol>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">Copy Codefor L from 2 to n:</span><br><span class="line">    for i from 1 to n-L+1:</span><br><span class="line">        j = i+L-1</span><br><span class="line">        dp[i][j] = INF</span><br><span class="line">        for k from i to j-1:</span><br><span class="line">            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j])</span><br><span class="line">return dp[1][n]</span><br></pre></td></tr></table></figure>

<ol>
<li><strong>双核处理问题</strong>：</li>
</ol>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">Copy Codev = sum / 2</span><br><span class="line">for i from 1 to n:</span><br><span class="line">    for j from 1 to v:</span><br><span class="line">        if a[i] &gt; j:</span><br><span class="line">            dp[i][j] = dp[i-1][j]</span><br><span class="line">        else:</span><br><span class="line">            dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i]] + a[i])</span><br><span class="line">return 1024 * (sum - dp[n][v])</span><br></pre></td></tr></table></figure>

<h4 id="五、算法时间和空间复杂度分析"><a href="#五、算法时间和空间复杂度分析" class="headerlink" title="五、算法时间和空间复杂度分析"></a>五、算法时间和空间复杂度分析</h4><ol>
<li><strong>最大子段和问题</strong>：时间复杂度O(n)，空间复杂度O(n)。</li>
<li><strong>矩阵连乘问题</strong>：时间复杂度O(n^3)，空间复杂度O(n^2)。</li>
<li><strong>双核CPU任务处理问题</strong>：时间复杂度O(n^2)，空间复杂度O(n^2)。</li>
</ol>
<h4 id="六、错误记录和解决"><a href="#六、错误记录和解决" class="headerlink" title="六、错误记录和解决"></a>六、错误记录和解决</h4><ol>
<li><strong>双核处理问题</strong>：最初尝试贪心策略，未找到全局最优解，改用动态规划解决。</li>
</ol>

      
    </div>
    <footer class="article-footer">
      <a data-url="https://gitee.com/lanceluot/blog.git/2024/05/01/%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E4%B8%8E%E5%88%86%E6%9E%90%E5%AE%9E%E9%AA%8C%E4%B8%89-%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/" data-id="clvnfbuue0001g05b2ve58bqg" data-title="算法设计与分析实验三-动态规划" class="article-share-link"><span class="fa fa-share">Teilen</span></a>
      
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/blog/tags/%E5%AE%9E%E9%AA%8C3/" rel="tag">实验3</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
  
    <a href="/blog/2024/05/01/%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%AE%9E%E9%AA%8C3-%E6%96%87%E4%BB%B6io%E7%BC%96%E7%A8%8B/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Älter</strong>
      <div class="article-nav-title">嵌入式实验3-文件io编程</div>
    </a>
  
</nav>

  
</article>


</section>
        
          <aside id="sidebar">
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Kategorien</h3>
    <div class="widget">
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/blog/categories/%E8%AE%A1%E7%AE%97%E6%9C%BA/">计算机</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tags</h3>
    <div class="widget">
      <ul class="tag-list" itemprop="keywords"><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/BUG/" rel="tag">BUG</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/RPC/" rel="tag">RPC</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/git/" rel="tag">git</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/java/" rel="tag">java</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/java%E5%90%8E%E7%AB%AF%E5%BC%80%E5%8F%91/" rel="tag">java后端开发</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/java%E6%BA%90%E7%A0%81/" rel="tag">java源码</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/jvm/" rel="tag">jvm</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/leetcode/" rel="tag">leetcode</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/leetcode%E9%A2%98%E8%A7%A3/" rel="tag">leetcode题解</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/rabbitmq/" rel="tag">rabbitmq</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/redis/" rel="tag">redis</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/shell/" rel="tag">shell</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/spring/" rel="tag">spring</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/springboot/" rel="tag">springboot</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/test/" rel="tag">test</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E4%BD%9C%E4%B8%9A/" rel="tag">作业</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E5%AE%9E%E9%AA%8C/" rel="tag">实验</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E5%AE%9E%E9%AA%8C3/" rel="tag">实验3</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E6%84%9F%E6%83%B3/" rel="tag">感想</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" rel="tag">操作系统</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/" rel="tag">数据结构与算法</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E6%B5%8B%E8%AF%95/" rel="tag">测试</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E7%96%91%E9%97%AE/" rel="tag">疑问</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E7%AC%94%E8%AE%B0/" rel="tag">笔记</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E7%AE%97%E6%B3%95/" rel="tag">算法</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/" rel="tag">设计模式</a></li><li class="tag-list-item"><a class="tag-list-link" href="/blog/tags/%E9%97%AE%E9%A2%98/" rel="tag">问题</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tag Cloud</h3>
    <div class="widget tagcloud">
      <a href="/blog/tags/BUG/" style="font-size: 10px;">BUG</a> <a href="/blog/tags/RPC/" style="font-size: 10px;">RPC</a> <a href="/blog/tags/git/" style="font-size: 10px;">git</a> <a href="/blog/tags/java/" style="font-size: 20px;">java</a> <a href="/blog/tags/java%E5%90%8E%E7%AB%AF%E5%BC%80%E5%8F%91/" style="font-size: 10px;">java后端开发</a> <a href="/blog/tags/java%E6%BA%90%E7%A0%81/" style="font-size: 10px;">java源码</a> <a href="/blog/tags/jvm/" style="font-size: 10px;">jvm</a> <a href="/blog/tags/leetcode/" style="font-size: 10px;">leetcode</a> <a href="/blog/tags/leetcode%E9%A2%98%E8%A7%A3/" style="font-size: 15px;">leetcode题解</a> <a href="/blog/tags/rabbitmq/" style="font-size: 10px;">rabbitmq</a> <a href="/blog/tags/redis/" style="font-size: 10px;">redis</a> <a href="/blog/tags/shell/" style="font-size: 10px;">shell</a> <a href="/blog/tags/spring/" style="font-size: 10px;">spring</a> <a href="/blog/tags/springboot/" style="font-size: 10px;">springboot</a> <a href="/blog/tags/test/" style="font-size: 10px;">test</a> <a href="/blog/tags/%E4%BD%9C%E4%B8%9A/" style="font-size: 10px;">作业</a> <a href="/blog/tags/%E5%AE%9E%E9%AA%8C/" style="font-size: 15px;">实验</a> <a href="/blog/tags/%E5%AE%9E%E9%AA%8C3/" style="font-size: 10px;">实验3</a> <a href="/blog/tags/%E6%84%9F%E6%83%B3/" style="font-size: 10px;">感想</a> <a href="/blog/tags/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/" style="font-size: 10px;">操作系统</a> <a href="/blog/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/" style="font-size: 10px;">数据结构与算法</a> <a href="/blog/tags/%E6%B5%8B%E8%AF%95/" style="font-size: 10px;">测试</a> <a href="/blog/tags/%E7%96%91%E9%97%AE/" style="font-size: 10px;">疑问</a> <a href="/blog/tags/%E7%AC%94%E8%AE%B0/" style="font-size: 10px;">笔记</a> <a href="/blog/tags/%E7%AE%97%E6%B3%95/" style="font-size: 10px;">算法</a> <a href="/blog/tags/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F/" style="font-size: 15px;">设计模式</a> <a href="/blog/tags/%E9%97%AE%E9%A2%98/" style="font-size: 10px;">问题</a>
    </div>
  </div>

  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Archiv</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2024/05/">May 2024</a></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2024/04/">April 2024</a></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2024/03/">March 2024</a></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2024/02/">February 2024</a></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2024/01/">January 2024</a></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2023/10/">October 2023</a></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2023/09/">September 2023</a></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2023/08/">August 2023</a></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2023/05/">May 2023</a></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2023/04/">April 2023</a></li><li class="archive-list-item"><a class="archive-list-link" href="/blog/archives/2022/12/">December 2022</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">letzter Beitrag</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/blog/2024/05/01/%E7%AE%97%E6%B3%95%E8%AE%BE%E8%AE%A1%E4%B8%8E%E5%88%86%E6%9E%90%E5%AE%9E%E9%AA%8C%E4%B8%89-%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/">算法设计与分析实验三-动态规划</a>
          </li>
        
          <li>
            <a href="/blog/2024/05/01/%E5%B5%8C%E5%85%A5%E5%BC%8F%E5%AE%9E%E9%AA%8C3-%E6%96%87%E4%BB%B6io%E7%BC%96%E7%A8%8B/">嵌入式实验3-文件io编程</a>
          </li>
        
          <li>
            <a href="/blog/2024/04/30/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E5%AE%9E%E8%B7%B5-%E5%AE%9E%E7%8E%B0%E4%B8%80%E4%B8%AAfat12%E6%96%87%E4%BB%B6%E7%B3%BB%E7%BB%9F/">操作系统实践-实现一个fat12文件系统</a>
          </li>
        
          <li>
            <a href="/blog/2024/04/25/LambdaQuery-%E5%92%8C-Query%E7%9A%84%E5%8C%BA%E5%88%AB/">LambdaQuery 和 Query的区别</a>
          </li>
        
          <li>
            <a href="/blog/2024/04/25/LambdaQuery%E5%92%8CQuery%E7%9A%84%E5%8C%BA%E5%88%AB/">LambdaQuery和Query的区别</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      
      &copy; 2024 myself<br>
      Powered by <a href="https://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>

    </div>
    <nav id="mobile-nav">
  
    <a href="/blog/" class="mobile-nav-link">Home</a>
  
    <a href="/blog/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    


<script src="/blog/js/jquery-3.6.4.min.js"></script>



  
<script src="/blog/fancybox/jquery.fancybox.min.js"></script>




<script src="/blog/js/script.js"></script>





  </div>
</body>
</html>